import java.util.*;

public class Solution {
    static int prev = Integer.MIN_VALUE;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    ///////////////////////////////////////////////////////////
    //每个节点的任务：左右子树及自身进行剪枝，然后返回给父节点
    //返回节点，父节点根据返回值是否为空来判断是否剪枝
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.val == 0 && root.left == null && root.right == null) return null;
        return root;
    }
    ///////////////////////////////////////////////////////////
    public static boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        boolean left = isValidBST(root.left);
        if(!left) return false;
        boolean cur = false;
        if(prev < root.val) cur = true;
        prev = root.val;
        if(!cur) return false;
        boolean right = isValidBST(root.right);

        return isValidBST(root.left) && isValidBST(root.right) && cur;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node2.left = node1;
        node2.right = node3;
        isValidBST(node2);
        StringBuilder sb = new StringBuilder();

        sb.deleteCharAt(sb.length()-1);
        String str = new String();
        str += "a";
    }


}
